// Copyright [2020] <unknown>
#include <bits/stdc++.h>
using namespace std;
// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

#define sz(x) ((int)x.size())

typedef long long LL;

const int N = 1e2+50;

namespace mcf {
    const int N = 1e5+50;
    template<typename T>
    struct E {
        int to, cp;
        T cost;
        int rev;
        E(int to=0, int cp=0, T cost=0, int rev=0):to(to), cp(cp), cost(cost), rev(rev){}
    };

    template<typename T>
    struct Mcmf {
        int v, prev[N], pree[N];
        T h[N], dis[N];
        vector<E<T>> G[N];
        void init(int n) {
            v = n;
            for (int i=0; i<=v; ++i)
                G[i].clear();
        }
        void addEdge(int from, int to, int cp, T cost) {
            G[from].emplace_back(to, cp, cost, G[to].size());
            G[to].emplace_back(from, 0, -cost, G[from].size()-1);
        }
        T go(int s, int t, int f, int &flow) {
            const T INF = 0x3f3f3f3f;
            T res = 0;
            memset(h, 0, sizeof (h[0]) * (v + 1));
            while (f) {
                priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> q;
                fill(dis, dis+v+1, INF);
                dis[s] = 0;
                q.emplace(0, s);
                while (!q.empty()) {
                    auto now = q.top();
                    q.pop();
                    int v = now.second;
                    if (dis[v] < now.first)
                        continue;
                    for (int i=0; i<sz(G[v]); ++i) {
                        auto &e = G[v][i];
                        if (e.cp > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to]) {
                            dis[e.to] = dis[v] + e.cost + h[v] - h[e.to];
                            prev[e.to] = v;
                            pree[e.to] = i;
                            q.emplace(dis[e.to], e.to);
                        }
                    }
                }
                if (dis[t] == INF)
                    break;
                for (int i=0; i<=v; ++i)
                    h[i] += dis[i];
                int d = f;
                for (int v=t; v!=s; v=prev[v])
                    d = min(d, G[prev[v]][pree[v]].cp);
                f -= d;
                flow += d;
                res += d * h[t];
                for (int v=t; v!=s; v=prev[v]) {
                    auto &e = G[prev[v]][pree[v]];
                    e.cp -= d;
                    G[v][e.rev].cp += d;
                }
            }
            return res;
        }
    };
}

using mcf::Mcmf;

Mcmf<int> mcmf;

int t, n, m;

char s[N][N];

// int id[N][N];
int in[N][N], out[N][N];


int main(int argc, char const *argv[]) {
    // code
    scanf("%d", &t);
    for (int kk=0; kk<t; ++kk) {
        scanf("%d%d", &m, &n);
        for (int i=0; i<n; ++i) {
            scanf("%s", s[i]);
        }
        int tot = 0;
        for (int i=0; i<n; ++i)
            for (int j=0; j<m; ++j) {
                // id[i][j] = tot++;
                in[i][j] = tot++;
                out[i][j] = tot++;
            }
        mcmf.init(tot);
        // dbg(n, m, tot);
        for (int i=0; i<n; ++i) {
            for (int j=0; j<m; ++j) {
                mcmf.addEdge(in[i][j], out[i][j], 1, -(s[i][j] == '*'));
                mcmf.addEdge(in[i][j], out[i][j], 1, 0);
                if (j+1<m && s[i][j+1] != '#')
                    mcmf.addEdge(out[i][j], in[i][j+1], 2, 0);
                if (i+1<n && s[i+1][j] != '#')
                    mcmf.addEdge(out[i][j], in[i+1][j], 2, 0);
            } 
        }

        int S = in[0][0], T = out[n-1][m-1];
        int f = 0;
        int cost = mcmf.go(S, T, 2, f);
        printf("%d\n", -cost);
    }
    return 0;
}
